package test;

//在D天内送达包裹的能力：https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/
//时间复杂度：O(n*log(sum))
public class ShipWithinDays {
	//返回在承载能力为limit时，装完所有重量货物所需要的天数
    public int f(int[] nums,long limit){
        long sum=0;
        int days=1;
        for(int i=0;i<nums.length;i++){
            if(nums[i]>limit) 
                return Integer.MAX_VALUE;
            if(sum+nums[i]>limit){
                days++;
                sum=nums[i];
            }
            else{
                sum+=nums[i];
            }
        }
        return days;
    }
    public int shipWithinDays(int[] weights, int days) {
        long sum=0;
        for(int i=0;i<weights.length;i++){
            sum+=weights[i];
        }
        //二分区间：[1,sum]
        long l=1,r=sum;
        long ret=0;
        while(l<=r){
            long mid=l+(r-l)/2;
            if(f(weights,mid)<=days){
                r=mid-1;
                ret=mid;
            }
            else{
                l=mid+1;
            }
        }
        return (int)ret;
    }
}
